/*************************************************************************
 * File Name:    test.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 02 Nov 2013 04:22:02 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Reverse Linked List II
 | Reverse a linked list from position m to n. Do it in-place and in one-pass.
 |
 | For example:
 | Given 1->2->3->4->5->NULL, m = 2 and n = 4,
 | return 1->4->3->2->5->NULL.
 |
 | Note:
 | Given m, n satisfy the following condition:
 | 1 ≤ m ≤ n ≤ length of list.
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n)
    {
        ListNode *left_tail = NULL;
        ListNode *pre, *t, *tmp;
        ListNode *reverse_tail = NULL;
        int cnt = 0;
        
        t = head;
        while (t != NULL) {
            ++cnt;
            
            if (cnt == m - 1) left_tail = t;
            if (cnt == m) pre = reverse_tail = t;
            
            if (cnt > m && cnt <= n) {
                tmp = t->next;
                t->next = pre;
                pre = t;
                t = tmp;
                
                if (cnt == n) {
                    reverse_tail->next = t;
                    if (left_tail != NULL) {
                        left_tail->next = pre;
                        return head;
                    }
                    return pre; 
                }
            } else {
                t = t->next;
            }
        }
        return head;
    }
};
